797D - Broken BST - CodeForces Solution

// https://codeforces.com/contest/797/problem/D
#include <bits/stdc++.h>
using namespace std;

int vals[100005];
pair<int, int> children[100005];
map<int, int> occ;
map<int, bool> works;

void dfs(int index, int left, int right) {
  if (left < vals[index] && vals[index] < right) {
    works[vals[index]] = true;
  }
  if (children[index].first != -2) {
    dfs(children[index].first, left, min(right, vals[index]));
  }
  if (children[index].second != -2) {
    dfs(children[index].second, max(left, vals[index]), right);
  }
}

int main() {
  cin.tie(NULL)->sync_with_stdio(false);
  int n;
  cin >> n;

  for (int i = 0; i < n; i++) {
    cin >> vals[i] >> children[i].first >> children[i].second; 
    occ[vals[i]]++;
    works[vals[i]] = false;
    children[i].first--;
    children[i].second--;
  }

  // find root
  int root = 0;
  bool root_poss[n] = {};
  for (int i = 0; i < n; i++) {
    if (children[i].first != -2) root_poss[children[i].first] = true;
    if (children[i].second != -2) root_poss[children[i].second] = true;
  }
  for (int i = 0; i < n; i++) if (root_poss[i] == false) root = i;

  // dfs, keep track of range of vals
  dfs(root, -2, 1000000001);

  int out = 0;
  for (auto thing : works) {
    if (!thing.second) out += occ[thing.first];
  }
  cout << out;
}